package ai.zixing.mashibing.new_class.class06;

import java.util.HashMap;

// https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
//  从前序与中序遍历序列构造二叉树
public class Code05_ConstructBinaryTreeFromPreorderAndInorderTraversal {
    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int value) {
            val = value;
        }
    }

    public TreeNode buildTree(int[] pre, int[] in) {
        if (pre == null || in == null || pre.length != in.length) {
            return null;
        }
        return f(pre, 0, pre.length - 1, in, 0, in.length - 1);
    }

    // 有一颗树，先序结果是 pre[L1...R1],中心结果是 in[L2...R2]
    // 返回整棵树的头节点
    public static TreeNode f(int[] pre, int L1, int R1, int[] in, int L2, int R2) {
        // 处理特殊情况，左树为空，或者有树为空
        // 先 【1，2，3】
        // 中 【1，2，3】
        if (L1 > R1) {
            return null;
        }
        // 先序遍历第一个节点就是头节点
        TreeNode head = new TreeNode(pre[L1]);
        // 只有一个节点
        if (L1 == R1) {
            return head;
        }
        // find 为中序遍历中的头节点，从 L2 开始找
        int find = L2;
        while (in[find] != pre[L1]) {
            find++;
        }
        // 左树中在中序遍历中的范围为[L2, find -1]
        // find - L2 是中序中左树的节点数则先序遍历中R1 = L1 + (find -L2)
        head.left = f(pre, L1 + 1, L1 + find - L2, in, L2, find - 1);
        head.right = f(pre, L1 + find - L2 + 1, R1, in, find + 1, R2);
        return head;
    }

    public TreeNode buildTree2(int[] pre, int[] in) {
        if (pre == null || in == null || pre.length != in.length) {
            return null;
        }
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < in.length; i++) {
            map.put(in[i], i);
        }
        return f2(pre, 0, pre.length - 1, in, 0, in.length - 1, map);
    }



    // 有一颗树，先序结果是 pre[L1...R1],中心结果是 in[L2...R2]
    // 返回整棵树的头节点
    public static TreeNode f2(int[] pre, int L1, int R1, int[] in, int L2, int R2, HashMap<Integer, Integer> map) {
        // 处理特殊情况，左树为空，或者有树为空
        // 先 【1，2，3】
        // 中 【1，2，3】
        if (L1 > R1) {
            return null;
        }
        // 先序遍历第一个节点就是头节点
        TreeNode head = new TreeNode(pre[L1]);
        // 只有一个节点
        if (L1 == R1) {
            return head;
        }
        int find = map.get(pre[L1]);
        // 左树中在中序遍历中的范围为[L2, find -1]
        // find - L2 是中序中左树的节点数则先序遍历中R1 = L1 + (find -L2)
        head.left = f2(pre, L1 + 1, L1 + find - L2, in, L2, find - 1, map);
        head.right = f2(pre, L1 + find - L2 + 1, R1, in, find + 1, R2, map);
        return head;
    }
}
